package leetcode;

import java.util.Arrays;

//分糖果
public class Candy {

	public static void main(String[] args) {
		Candy object = new Candy();
		int[] ratings = {1, 3, 4, 3, 3, 3, 2, 2, 1};
		object.candy2(ratings);
	}
	
	// 思想来自于https://discuss.leetcode.com/topic/37924/very-simple-java-solution-with-detail-explanation
	public int candy(int[] ratings) {
		int[] candys = new int[ratings.length];
		Arrays.fill(candys, 1); // 每个孩子最少一个糖果
		// 从左到右循环找出满足大于左边的rating
		for (int i = 0; i < ratings.length - 1; i++) {
			if (ratings[i] < ratings[i + 1]) {
				candys[i + 1] = candys[i] + 1; // reating大的糖果数加1
			}
		}
		// 从右到左
		for (int i = ratings.length - 1; i > 0; i--) {
			//注意，这里除了要比较rating是否大于之外，还需要判断是否candy也比左边的大了
			if (ratings[i - 1] > ratings[i]) {
				if (candys[i - 1] < candys[i] + 1) {
					candys[i - 1] = candys[i] + 1; // reating大的糖果数加1
				}
			}
		}
		int sum = 0;
		for (int i = 0; i < candys.length; i++) {
			sum += candys[i];
		}
		return sum;
	}
	
	//如果保证得分数一样时，所分得的糖果必须一致
	public int candy2(int[] ratings) {
		int[] candys = new int[ratings.length];
		Arrays.fill(candys, 1); // 每个孩子最少一个糖果
		// 从左到右循环找出满足大于左边的rating
		for (int i = 0; i < ratings.length - 1; i++) {
			if (ratings[i] < ratings[i + 1]) {
				candys[i + 1] = candys[i] + 1; // reating大的糖果数加1
			}else if(ratings[i] == ratings[i + 1]){
				//如果相等那么就维持一样的
				candys[i + 1] = candys[i];
			}
		}
		// 从右到左
		for (int i = ratings.length - 1; i > 0; i--) {
			//注意，这里除了要比较rating是否大于之外，还需要判断是否candy也比左边的大了
			if (ratings[i - 1] > ratings[i]) {
				//左程云书上说的是判断上坡的坡度和下坡的坡度，其实这个也是一样的意思
				//通过比较candys[i - 1] 和 candys[i] + 1的大小来判断坡度
				if (candys[i - 1] < candys[i] + 1) {
					candys[i - 1] = candys[i] + 1; // reating大的糖果数加1
				}
			}else if(ratings[i - 1] == ratings[i]){
				if (candys[i - 1] < candys[i]) {
					candys[i - 1] = candys[i];
				}
			}
		}
		int sum = 0;
		for (int i = 0; i < candys.length; i++) {
			System.out.print("  " + candys[i]);
			sum += candys[i];
		}
		return sum;
	}
}
